Statement#

Given strings s1, s2, and s3, find whether an interleaving of s1 and s2 forms s3.

An interleaving of two strings a and b is a configuration where a and b splits into nn and mm substrings, respectively, such that:

  • a =a1= a_{1} + a2a_{2} + … + ana_{n}
  • b =b1= b_{1} + b2b_{2} + … + bmb_{m}
  • nm1\left | n - m \right | \leqslant 1
  • The interleaving can follow either of the following two formats:
    • a1+b1+a2+b2+a3+b3+...a_{1} + b_{1} + a_{2} + b_{2} + a_{3} + b_{3} + ...
    • b1+a1+b2+a2+b3+a3+...b_{1} + a_{1} + b_{2} + a_{2} + b_{3} + a_{3} + ...
  • axa_{x} can be a consecutive sequence of characters in string s1.
  • bxb_{x} can be a consecutive sequence of characters in string s2.

Note: a+ba + b is the concatenation of the strings aa and bb.

Let’s say we have two strings, “abc” and “xyz”. We may interleave them in multiple ways. We may alternately pick one character from each string until we have used up all the characters, giving us “axbycz” and “xaybzc”. Or, we may try to pick two characters at a time from each string, giving us “abxycz” and “xyabzc”. If we pick three characters at a time, we get “abcxyz” and “xyzabc”. Another class of variations is to pick a variable number of characters from each string, which leads to many more possibilities, such as “abxcyz”, “xayzbc”, and so on. However, “bxaycz” is not a valid interleaving, as the order of the characters taken from the first string is not preserved, since “b” appears here before “a”. Similarly, “acxybz” is not a valid interleaving.

Constraints:

  • 00 \leq s1.length, s2.length 375\leq 375
  • 00 \leq s3.length 750\leq 750
  • s1, s2, and s3 consist of lowercase English letters.

Examples#

No.

s1

s2

s3

Output

1

"xyz"

"abc"

"axbycz"

True

2

"abc"

"xyz"

"axbycz"

True

3

"abc"

"xyz"

"xaybzc"

True

4

"xxyzz"

"wyyzx"

"xxwyyyxzzz"

False

5

""

""

""

True

6

"abd"

"cef"

"adcbef"

False

Try it yourself#

Implement your solution in the following playground:

Python
usercode > main.py
Input #1
Input #2
Input #3
Interleaving Strings

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach#

A naive approach to deduce if s3 is indeed a result of interleaving s1 and s2 is to try and match the two strings with s3 one letter at a time. As an example, suppose we have the following strings:

  • s1 = “abc”
  • s2 = “xyz”
  • s3 = “abxycz”

The first step is to verify if the length of s3 is equal to the sum of the lengths of s1 and s2. If it isn’t, return FALSE as the output. However, that isn’t the case for the given inputs. Therefore, we can traverse these strings and engage in the matching process. While traversing, we keep track of the indexes we are at in all three strings, allowing us to check the order in which these characters appear. Let’s see how it will work in this example with the help of the illustration below:

Created with Fabric.js 3.6.6 a b c x y z x a y b c z 0 0 0 s1 s2 s3 There are two possibilities: The character the s1 index is currently pointing towill be the first character of s3, or the character the s2 index is pointing to willbe the first character of s3. If both these cases fail, then return FALSE. s1 index s2 index s3 index

1 of 13

Created with Fabric.js 3.6.6 a b c 0 0 0 x y z x a y b c z s1 s2 s3 s1 index s2 index s3 index The character the s2 index points to is the first character of s3. Hence, increment both the s2 index and s3 index by one.

2 of 13

Created with Fabric.js 3.6.6 a b c 0 x y z 1 1 x a y b z c s1 s2 s3 s1 index s2 index s3 index Compare the character s3 index is pointing to with the characters that s1 indexor s2 index are pointing to.

3 of 13

Created with Fabric.js 3.6.6 x y z 1 0 1 a b c x a y b z c s1 s2 s3 s1 index s2 index s3 index The character s1 index is pointing to is the character s3 index is pointing to.Hence, increment both the s1 index and s3 index by one.

4 of 13

Created with Fabric.js 3.6.6 x y z 1 a b c 1 2 x a y b z c s1 s2 s3 s1 index s2 index s3 index Compare the character s3 index is pointing to with the characters that s1 indexor s2 index are pointing to.

5 of 13

Created with Fabric.js 3.6.6 a b c 1 1 2 x y z x a y b z c s1 s2 s3 s1 index s2 index s3 index The character s2 index is pointing to is the character s3 index is pointing to.Hence, increment both the s2 index and the s3 index by one.

6 of 13

Created with Fabric.js 3.6.6 a b c 1 x y z 2 3 x a y b z c s1 s2 s3 s1 index s2 index s3 index Compare the character s3 index is pointing to with the characters that s1 indexor s2 index are pointing to.

7 of 13

Created with Fabric.js 3.6.6 x y z 2 1 3 a b c x a y b z c s1 s2 s3 s1 index s2 index s3 index The character s1 index is pointing to is the character s3 index is pointing to.Hence, increment both s1 index and s3 index by one.

8 of 13

Created with Fabric.js 3.6.6 x y z 2 a b c 2 4 x a y b z c s1 s2 s3 s1 index s2 index s3 index Compare the character s3 index is pointing to with the characters that s1 indexor s2 index are pointing to.

9 of 13

Created with Fabric.js 3.6.6 a b c 2 2 4 x y z x a y b z c s1 s2 s3 s1 index s2 index s3 index The character s2 index is pointing to is the character s3 index is pointing to.Hence, increment both s2 index and s3 index by one.

10 of 13

Created with Fabric.js 3.6.6 a b c 2 x y z x a y b z c 3 5 s1 s2 s3 s1 index s2 index s3 index We will again compare the character s3 index is pointing at with thecharacter s1 index or s2 index are pointing to. However, a key detailto take into account is that we have traversed the entirety of s2, thatmeans that we can only search for the remaining characters of s3 in s1.

11 of 13

Created with Fabric.js 3.6.6 x y z 3 2 5 a b c x a y b z c s1 s2 s3 s1 index s2 index s3 index The character s1 index is pointing to is the character s3 index is pointing to.Hence, increment both s1 index and s3 index by one.

12 of 13

Created with Fabric.js 3.6.6 x y z 3 a b c x a y b z c 3 6 s1 s2 s3 s1 index s2 index s3 index We have reached the end of the string and since every index is equal to thelength of it's respective string, we can return TRUE as our output.

13 of 13

As we can see, we have two options at any step:

  • If the letter at s1 index matches with the letter at s3 index, we consume both, that is, we move s1 index as well as s3 index one step forward. The matching process continues recursively for the portions of s1, s2, and s3 that we have not yet considered.
  • If the letter at s2 index matches with the letter at s3 index, we consume both, that is, we move s2 index as well as s3 index one step forward. The matching process continues recursively for the portions of s1, s2, and s3 that we have not yet considered.

This process allows us to check all possible combinations of interleaving.

Let’s implement this naive approach:

Interleaving Strings using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the above algorithm is O(2s+t)O(2^{s+t}), where s and t are the lengths of s1 and s2, respectively.

Space complexity#

The space complexity of this naive approach is O(s+t)O(s + t), where ss and tt are the lengths of s1 and s2, respectively. The solution uses the stack to store the data for each recursive call, and there may be at most s+ts + t calls in any given branch of the recursive call tree.

Optimized solution using dynamic programming#

As the naive approach is costly in terms of time complexity, we can try to optimize the solution using dynamic programming. Let’s see if this problem satisfies both conditions of dynamic programming:

  • Optimal substructure: When we are presented with the problem of checking whether two strings, s1 and s2 have been interleaved to create s3, we compare the first character of s1 with the first character of s3, and if they match, we check the remaining characters of s1, the original characters of s2, and the remaining characters of s3. Denoting the length of s1 by n1n_1, the length of s2 by n2n_2 and the length of s3 by n3n_3, we can see that solving the problem for {n1,n2,n3}\{n_1, n_2, n_3\} involves solving the smaller problem, {n11,n2,n31}\{n_1-1, n_2, n_3-1\}. In case it’s the first character of s2 that matches the first character of s3, we consume these matching characters and check the original characters of s1, the remaining characters of s2 and the remaining characters of s3. That is, we now need to solve the smaller problem represented by {n1,n21,n31}\{n_1, n_2-1, n_3-1\}. As solving a smaller version of the overall problem helps to solve it, this problem has the optimal substructure property.

  • Overlapping subproblems: The following illustration highlights the overlapping subproblems. There are two recursive calls for s1 = “b”, s2 = “b”, s3 = “bb” (highlighted in peach), four calls for s1 = “”, s2 = “”, s3 = “” (highlighted in green), and so on. The function is computing certain results over and over again, which is inefficient. Therefore, this problem has the overlapping subproblems property.

Overlapping subproblems
Overlapping subproblems

Top-down solution#

The top-down solution improves on the recursive solution. Instead of repeatedly solving the same problems, we store the result of each subproblem and reuse it when needed. Let’s look at an example that would demonstrate this phenomenon:

  • s1 = “ab”
  • s2 = “ab”
  • s3 = “aabb”

As illustrated above, the recursive solution involves solving several overlapping subproblems. However, it can be optimized with the help of memoization. In the recursive function, the indexes of s1, s2, and s3 uniquely identify each subproblem. So, we can store these subproblems in a hash table indexed by s1, s2, and s3 and look them up when required.

Let’s implement this memoization approach:

Interleaving Strings using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this approach is O(s×t)O\left ( s \times t \right ) where ss and tt are the lengths of s1 and s2, respectively.

Space complexity#

The space complexity would be O(s×t)O\left ( s \times t \right ) as we use a hash table of size s×ts \times t to store the subproblems we solve.

Bottom-up solution#

The first step of our bottom-up solution is to check if the lengths of s1 and s2 add up to the length of s3. If this is not the case, then s3 cannot be an interleaving of s1 and s2, so we can return FALSE without proceeding further.

If we pass the initial test then we can move on to constructing our solution. The bottom-up solution starts with the initialization of our lookup table. The lookup_table is created with an extra row and column to separate the base cases from the rest of the subproblems that we will solve later. The base cases for the problem are as follows:

  • The top-left cell (s1_index = 0 and s2_index = 0) represents the case where the interleaved string s3 is empty. This cell will be TRUE if both s1 and s2 are empty.

  • For the first column (s1_index > 0 and s2_index = 0), each cell will be filled with TRUE as long as the prefix of s3 up to that point is equal to the current substring of s1 (s1[0]…s1[s1_index - 1]). This is because, in this case, s2 is empty, so all the characters in s3 must come from s1.

  • For the first row (s1_index = 0 and s2_index > 0), each cell will be filled with TRUE as long as the prefix of s3 up to that point is equal to the current substring of s2 (s2[0]…s2[s2_index - 1]). This is because, in this case, s1 is empty, so all the characters in s3 must come from s2.

As the base case logic outlined above indicates, each cell in the lookup table, addressed by the tuple (s1_index, s2_index), represents whether there is any way to interleave the initial s1_index characters of s1 with the initial s2_index characters of s2 to form the string represented by the initial s1_index + s2_index characters of s3.

Let’s see what we mean by this with a couple of examples:

  1. Given s1 = “uvx”, s2 = “wyz” and s3 = “uvwxyz”, lookup_table[2][1] represents whether there is any way to interleave the initial 22 characters from s1, “uv”, and the initial character from s2, “w”, to make “uvw”, the initial 2+1=32+1=3 characters in s3. Since this is possible, the result of this subproblem is TRUE.

  2. Similarly, lookup_table[2][2] represents whether there is any way to interleave the initial 22 characters from s1, “uv”, and the initial 22 characters from s2, “wy”, to make “uvwx”, the initial 2+2=42+2=4 characters in s3. Since this is not possible, the result of this subproblem is FALSE.

Let’s walk through the process of checking whether the given strings, s1 and s2, are interleaved to form s3:

Created with Fabric.js 3.6.6 u v x w y z u v w x y z s1 s2 s3 s2 s1 We can always find a string that is empty tointerleave with s1 and s2 if they are bothempty. Therefore, we have a T already in placefor TRUE. w y z T F F F u F F F F v F F F F x F F F F

1 of 17

Created with Fabric.js 3.6.6 u v x w y z u v w x y z w y z T F F F u F F F F v F F F F x F F F F s1 s2 s3 s1 s2 We can't find a string to interleave with s1 and s2 if s1 is empty, s2 is "w" and s3 starts with a "u". Therefore, we have a F in place forFALSE.

2 of 17

Created with Fabric.js 3.6.6 u v x w y z u v w x y z w y z T F F F u F F F F v F F F F x F F F F s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s1 is empty, s2 is "wy" and s3 starts with a "uv". Therefore, we have a F in place for FALSE.

3 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u F F F F v F F F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s1 is empty, s2 is "wyz" and s3 starts with a "uvw". Therefore, we have a F in place for FALSE.

4 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v F F F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can find a string to interleave with s1 and s2 if s2 is empty, s1 is "u" and s3 starts with a "u". Therefore, we have a T in place for TRUE.

5 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T F F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can find a string to interleave with s1 and s2 if s2 is empty, s1 is "uv" and s3 starts with a "uv". Therefore, we have a `T` in place for TRUE.

6 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T F F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s2 is empty, s1 is "uvx" and s3 starts with a "uvw". Therefore, we have a `F` in place for FALSE.

7 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T F F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s1 is "u", s2 is "w" and s3 starts with a "uv" . Therefore, we have a `F` in place for FALSE.

8 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T F F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s1 is "u", s2 is "wy" and s3 starts with a "uvw". Therefore, we have a `F` in place for FALSE.

9 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T F F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s1 is "u", s2 is "wyz" and s3 starts with a "uvwx". Therefore, we have a `F` in place for FALSE.

10 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T T F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can find a string to interleave with s1 and s2 if s1 is "uv", s2 is "w" and s3 starts with a "uvw". Therefore, we have a `T` in place for TRUE.

11 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T T F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s1 is "uv", s2 is "wy" and s3 starts with a "uvwx". Therefore, we have a `F` in place for FALSE.

12 of 17

Created with Fabric.js 3.6.6 u v x w y z w y z T F F F u T F F F v T T F F x F F F F u v w x y z s1 s2 s3 s2 s1 We can't find a string to interleave with s1 and s2 if s1 is "uv", s2 is "wyz" and s3 starts with a "uvwxy". Therefore, we have a `F` in place for FALSE.

13 of 17

Created with Fabric.js 3.6.6 u v x w y z u v w x y z w y z T F F F u T F F F v T T F F x F T F F s1 s2 s3 s2 s1 We can find a string to interleave with s1 and s2 if s1 is "uvx", s2 is "w" and s3 starts with a "uvwx". Therefore, we have a `T` in place for TRUE.

14 of 17

Created with Fabric.js 3.6.6 u v x w y z u v w x y z w y z T F F F u T F F F v T T F F x F T T F s1 s2 s3 s2 s1 We can find a string to interleave with s1 and s2 if s1 is "uvx", s2 is "wy" and s3 starts with a "uvwxy". Therefore, we have a `T` in place for TRUE.

15 of 17

Created with Fabric.js 3.6.6 u v x w y z u v w x y z w y z T F F F u T F F F v T T F F x F T T T s1 s2 s3 s2 s1 We can find a string to interleave with s1 and s2 if s1 is "uvx", s2 is "wyz" and s3 starts with a "uvwxyz". Therefore, we havea `T` in place for TRUE.

16 of 17

Created with Fabric.js 3.6.6 u v x w y z u v w x y z w y z T F F F u T F F F v T T F F x F T T T s1 s2 s3 s2 s1 We can conclude that s3 is a product of interleaving s1 and s2.

17 of 17

We traverse the remaining cells of the table from top left to bottom right. We do this in the form of a nested loop where in the outer loop, s1_index ranges from 00 to [(length of s1)+1][(length \space of \space s1) + 1] and in the inner loop, s2_index ranges from 00 to [(length of s2)+1][(length \space of \space s2) + 1]. This nested loop allows us to consider all possible combinations of characters from s1 and s2 that can be used to form the interleaved string s3.

For each cell, there are two possibilities for matching the current prefix of s3, expressed as s3[0:s1_index + s2_index - 1]:

  1. Either we match with the current character from s1:

    • The value of lookup_table[s1_index][s2_index] is set to TRUE if the character s1[s1_index] is equal to the character s3[s1_index + s2_index - 1] and the previous characters in s1 up to the index s1_index-1 have already been matched with the corresponding characters in s3 (i.e., the value of the table at position lookup_table[s1_index - 1][s2_index] is TRUE).
  2. Or, we match with the current character from s2:

    • The value of lookup_table[s1_index][s2_index] is set to TRUE if the character s2[s2_index] is equal to the character s3[s1_index + s2_index - 1] and the previous characters in s2 up to the index s2_index-1 have already been matched with the corresponding characters in s3 (i.e., the value of the table at position lookup_table[s1_index][s2_index - 1] is TRUE).

Note: Since s1_index and s2_index are zero-indexed, we need to subtract 11 from the sum of s1_index and s2_index to get the correct index in s3. This is because the first character in s3 is at index 00, not index 11.

If either one of the two conditions above is TRUE, the result of the current subproblem is TRUE, and FALSE otherwise.

The above operations are repeated until we have traversed the table entirely.

After the table has been completely filled, the bottom-right cell contains TRUE if an interleaving of s1 and s2 forms s3. Otherwise, it will contain FALSE. Hence, we return the value of the bottom-right cell as the final result.

Let's implement this algorithm:

Interleaving String using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this approach is O(s×t)O\left ( s \times t \right ) where ss and tt are the lengths of s1 and s2, respectively.

Space complexity#

The space complexity of this approach is O(s×t)O\left ( s \times t \right ) where ss and tt are the lengths of s1 and s2, respectively.

Distinct Subsequence Pattern Matching

Word Break II